مساله معروف فروشنده دوره گرد کاربردهای فراوانی در توالی عملیات و زمان بندی دارد. الگوریتم های ابتکاری تعویض شاخه از جمله الگوریتم های ابتکاری سریعی است که هنوز هم جهت بدست آوردن حل نزدیک به بهینه مسأله متقارن فروشنده دوره گرد از آن استفاده می شود. در این مقاله روش جدیدی برای انتخاب شاخه ارائه شده که زمان محاسباتی الگوریتم های تعویض شاخه را به یک سوم زمان مورد نیاز کاهش می دهد بدون آنکه از کیفیت حل مساله بکاهد.

کار قبلی خود در مورد شاخص های پیچدگی مساله فروشنده دوره گرد را با استفاده از تکنیکهای طیفی گراف از بازیابی اطلاعات گسترش می دهیم. یک شاخص پیچیدگی پایایی از یک نمونه I است که توسط آن می توانیم زمان اجرای یک الگوریتم دقیق برای TSP برای I را پیش بینی کنیم. مساله فروشنده دوره گرد متقارن با نمونه های I را در نظر می گیریم که توسط گراف های کامل وزن دار G نمایش داده شده اند. شهودا، سختی نمونه G به نحوه توزیع یال های کوتاه G مرتبط است. بنابراین تعدادی از زیرگراف های یالی کوتاه از G (درخت فراگیر مینیمال و چندین گراف دیگر) به عنوان گرا فهای غیر وزن دار و چندین مورد پایا از آنها را به عنوان شاخص های پیچیدگی بالقوه در نظر می گیریم. در اینجا پایاهای طیفی (مانند شعاع طیفی ماتریس مجاورت) نقش مهمی را بازی می کند. الگوریتم های خوشه بندی طیفی به همراه اطلاعات به دست آمده از شکاف طیفی در طیف لاپلاسی زیر گراف های یال کوتاه به کار برده شده است.

مسیریابی یکی از مسائل بسیار پرکاربرد GIS است که هدف اصلی آن یافتن بهترین مسیر گذرنده از یک سری موقعیت های از پیش تعیین شده است. این فرایند می تواند تاثیر بسزایی در تصمیم گیری های حساس مکانی داشته باشد. به همین دلیل از دیرباز تحقیقات بسیاری در مورد بهینه سازی این مساله با استفاده از الگوریتم های مختلف صورت گرفته است. مساله فروشنده دوره گرد یکی از مسائل بسیار کهن در علوم کاربردی است که پیش از پیدایش GIS نیز مطرح بوده است. این مساله با ظهور فناوری های جدید مانند GIS کاربردهای بسیاری یافته و روش های جدیدی نیز برای حل آن پیشنهاد شده است. الگوریتم های تکاملی (ژنتیک) یکی از روش هایی هستند که برای حل مسائل بهینه سازی مختلف به کار گرفته می شوند. تحقیقات نشان داده است که تلفیق روش های جست وجوی محلی (Local Search) با عملگرهای ژنتیک می تواند منجر به نتایج بهتری در حل مساله فروشنده دوره گرد شود. در نوشتار حاضر، روشی تازه و ابتکاری برای حل مساله مسیریابی ارائه و پیاده سازی شده است. در این روش با بهره گیری از مفهوم مرکز هندسی به برازش چندضلعی ها با رئوس شهرها، به گونه ای پرداخته شده است که مسیر نهایی محدب ترین چندضلعی باشد. این الگوریتم با رویکردی پوششی با جهت بیرونی درونی بزرگ ترین دایره محیطی شهرها را به کوچک ترین چندضلعی محدب ممکن تبدیل می کند. همچنین با استفاده از جست وجوی محلی مبتنی بر الگوریتم ژنتیک و روش نزدیک ترین همسایه (NN)، به حل مساله مسیریابی فروشنده دوره گرد پرداخته شده است. ارزیابی نتایج حاصل از روش پیشنهادی با نتایج حاصل از روش های ژنتیکی، جست وجوی محلی و نزدیک ترین همسایه حاکی از این بود که روش پیشنهادی، سرعت و دقت بالایی را در تولید مسیرهای نهایی ارائه می کند. بررسی نتایج نهایی ژنتیک با روش ابتکاری نشان دادکه این الگوریتم همواره نمی تواند به جواب های بهتری برسد. مثلا در تعداد 25 بار اجرای جداگانه جست وجوی ژنتیک، 69.3 درصد از جواب ها از جواب روش پیشنهادی، بهتر نبودند. از طرف دیگر روش پیشنهادی می تواند چندین هزار برابر سریع تر از الگوریتم قدرتمند ژنتیک جواب های نهایی را تولید کند.

مساله کلاسیک فروشنده دوره گرد عبارت از تعیین توری است که کل مسافت یا هزینه بازدید چندین شهر را حداقل نماید و از هر شهر فقط یک بار عبور نماید و دوباره به نقطه شروع برگردد. این مقاله الگوریتم جدیدی را برای سرعت بخشیدن به اجرای محاسباتی الگوریتمهای ابتکاری تعویض شاخه برای مساله متقارن فروشنده دوره گرد ارایه می دهد. بهبود اجرا با در نظر گرفتن فقط تعویضاتی که یک شانس خوب برای ایجاد یک پاسخ بهتر را دارند، به دست می آید. این الگوریتم از سایر الگوریتمهای ابتکاری سریعتر می باشد و زمان محاسباتی آن خیلی کمتر از سایر الگوریتم ها می باشد. الگوریتم جدید امکان پاسخ دادن به مسایل فروشنده دوره گرد را در مقیاس بزرگ فراهم می سازد.

در این مقاله، یک روش ابتکاری برای یافتن یک تور خوب مساله فروشنده دوره گرد نامتقارن ارائه شده است. در این روش، ابتدا با استفاده از ماتریس نرمال سازی شده، سعی می شود توری ساخته شود که شهرهای تور به گونه ای انتخاب شوند تا درمراحل بعدی، از رفتن به شهرهای پرهزینه (مسافت یا زمان طولانی) پرهیز شود. سپس اندازه تور مذکور به کمک روش ابداعی، بهبود داده شده است. برای انجام این پژوهش، برنامه رایانه ای روش نرمال سازی ماتریس هزینه تخصیص خطی و روش پیشنهادی به زبان C++ نوشته شده و مسائل زیادی تا 500 شهر حل شده است. مسایل حل شده عبارتند از تعدادی مسائل تصادفی از نوع نامتقارن و تمامی مسایل محک فروشنده دوره گرد نامتقارن. نتایج بدست آمده حاکی از آن است که این روش، برای تمام مسایل آزمون شده، تور خیلی خوبی بدست می دهد.

یکی از کاربردی ترین مسایل بهینه سازی ترکیباتی مساله چندین فروشنده دوره گرد است که در آن،m>1 فروشنده از یک نقطه مشترک به نام انبار شروع به حرکت می کنند و بعد از ملاقات کردن n>m مشتری به آن باز می گردند، به طوری که هر مشتری تنها یک بار به وسیله یک فروشنده مورد ملاقات قرار می گیرد. هدف در این مساله کمینه کردن مسیر کلی پیموده شده توسط همه فروشنده های دوره گرد است. در این مقاله، یک روش اصلاحی الگوریتم نمونه مورچگان برای این مساله به کار گرفته می شود که در ضریب تشویق بهترین مسیر با الگوریتم معمولی نمونه مورچگان تفاوت دارد. این ضریب سبب می شود که الگوریتم دارای قدرت بیشتری برای فرار از نقاط بهینه محلی شود و بتواند به جواب های با کیفیت تری دست یابد. نتایج محاسباتی روی مثال های استاندارد به وضوح کارایی الگوریتم جدید را نسبت به الگوریتم های دیگر فراابتکاری نشان می دهد.